package listnode;

import listnode.data.ListNode;

import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;


/**
 * 两两交互链表中的节点 （抖音 三亚 2024）
 * （leetcode好像没有）
 * 栈+队列
 */
public class SwapNodesInPairs {


    public ListNode swapPairs(ListNode head) {
        Stack<ListNode> stack=new Stack<>();
        Queue<ListNode> queue = new LinkedList<>();

        ListNode cur=head;
        while(cur!=null){
            stack.push(cur);
            cur=cur.next;
            if (cur!=null){
                stack.push(cur);
                cur=cur.next;
            }
            while (!stack.empty()){
                ListNode first=stack.pop();
                queue.offer(first);
                if (!stack.empty()){
                    ListNode second=stack.pop();
                    queue.offer(second);
                }
            }
        }

        ListNode preHead=new ListNode(-1);
        ListNode newCur=preHead;
        while (!queue.isEmpty()){
            newCur.next=queue.poll();
            newCur=newCur.next;
        }
        newCur.next=null;

        return preHead.next;
    }

    public static void main(String[] args) {
        // 创建链表 [1,2,3,4]
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        head.next.next.next.next.next = new ListNode(6);
        head.next.next.next.next.next.next = new ListNode(7);


        SwapNodesInPairs solution = new SwapNodesInPairs();
        ListNode newHead = solution.swapPairs(head);

        // 打印交换后的链表
        ListNode current = newHead;
        while (current != null) {
            System.out.print(current.val + " ");
            current = current.next;
        }
    }


//    public ListNode swapPairs(ListNode head) {
//        // 创建虚拟头节点
//        ListNode dummy = new ListNode(-1);
//        dummy.next = head;
//        ListNode prev = dummy;
//
//        while (head != null && head.next != null) {
//            // 定义两个要交换的节点
//            ListNode firstNode = head;
//            ListNode secondNode = head.next;
//
//            // 交换节点
//            prev.next = secondNode;
//            firstNode.next = secondNode.next;
//            secondNode.next = firstNode;
//
//            // 更新指针
//            prev = firstNode;
//            head = firstNode.next;
//        }
//
//        return dummy.next;
//    }
}    